import time
import logging

import io.ioloop
import tx.comm_id
import verset

log = logging.getLogger('sched')

TIMEOUT_RES = 0.001

# queue priority: lower is higher
PRIORITY_LOWEST = 1000
PRIORITY_HIGH   = 0
PRIORITY_URGENT = -1000

#------------------------------------------------------------------------------
def get_time():
    """Redefine this function for testing purposes, if needed."""
    return time.time()

#------------------------------------------------------------------------------
class Scheduler:
    """Design
    
    The scheduler consists of a set of queues. Items can come off thte
    queue due to: a PULL event or a TIMEOUT.
    """

    def __init__(self, send_fcn):
        # queue name -> queue
        self.queues_ = {}
        self.scheme_ = {}

        # Set of requests seen from the transport layer
        self.reqs_ = []

        # send_fcn : comm_id, msg -> None
        self.send_fcn_ = send_fcn

    def activate_queues(self, c_id):
        """Register the queues if needed. Subclasses need to implement this to
        deal with queue creation."""
        raise NotImplementedError()

    def deactivate_queues(self, c_id):
        """Cleanup queues that are not needed. Subclasses should
        override this if they want to perform this kind of cleanup."""
        pass
    
    def add_queue(self, queue):
        if queue.name() in self.queues_:
            log.error('adding two queues %s, ignoring' % queue.name())
            return
        log.debug('added queue %s' % queue.name())
        self.queues_[queue.name()] = queue

    def add_scheme(self, scm):
        if scm.name() in self.scheme_:
            log.error('adding two schemes %s, ignoring' % scm.name())
            return
        log.debug('added scheme %s' % scm.name())
        self.scheme_[scm.name()] = scm

    def classify(self, msg, label):
        """Override this function to change how msgs are classified.

        @return Given a msg and a label, return a list of queues the
        msg should be placed on.

        Null implementation simply uses the label as the queue
        name.

        XXX/bowei -- classify needs actions as well. prepend/timeout etc.
        """
        return [label]

    def match_scheme(self, c_id):
        """Matches the scheme that should be used."""
        raise NotImplementedError()
        
    def schedule_msg(self, msg, label):
        """Given label and msg, place the msg in the appropriate
        queue."""
        qns = self.classify(msg, label)
        for qn in qns:
            if qn not in self.queues_:
                log.error("couldn't schedule %s:%s, classifier return bogus qn: %s" %
                          (msg, label, qn))
                return
            log.debug('%s:%s scheduled on q %s' % (msg, label, qn))
            self.queues_[qn].append(msg)

        # XXX/bowei -- this is really inefficient, but will do for now
        d = []
        for c_id in self.reqs_:
            scm = self.match_scheme(c_id)
            log.debug('schedule_msg: looking at scm %s' % scm)
            msg = self.pull_data(scm)
            if msg:
                self.send_fcn_(c_id, msg)
                d.append(c_id)
                break
        for c_id in d: self.reqs_.remove(c_id)
        
    def timeout(self, scheme):
        # XXX/bowei -- how to handle timeouts?
        raise NotImplementedError()
    
    def pull_data(self, scheme):
        """Pull returns a msg (if any) to be sent out"""
        qs = sorted([self.queues_[qn] for qn in self.scheme_[scheme].queues()],
                    lambda a, b: cmp(a.priority(), b.priority()))
        msg = None
        for q in qs:
            msg = q.pull()
            if msg is not None:
                break
        return msg

    def update(self, msg):
        """Update the scheduler queues with new data. Subclasses
        should override this for the appropriate behavior. By default
        this does nothing."""
        pass

    def check_reqs(self):
        """Return a list of all the messages to be sent from the queues."""
        to_send = []
        for c_id in self.reqs_:
            scm = self.match_scheme(c_id)
            msg = self.pull_data(scm)
            if msg:
                to_send.append((c_id, msg))
            else:
                break
        for i in to_send:
            self.send_fcn_(i[0], i[1])
            
    def req_data(self, c_id):
        """Signal that iface_id going to peer_id has capacity to
        deliver a message."""
        self.activate_queues(c_id)
        if c_id in self.reqs_:
            log.warn('multiple req_data for %s' % cid)
        scm = self.match_scheme(c_id)
        msg = self.pull_data(scm)
        if msg:
            self.send_fcn_(c_id, msg)
        else:
            self.reqs_.append(c_id)
            log.debug('req noted for %s' % c_id)

    def unset_req_iface(self, iface_id):
        """Remove all requests on interface iface_id"""
        d = []
        for t, i, p in self.reqs_:
            if i == iface_id:
                d.append((t, i,p))
        for c_id in d:
            self.reqs_.remove(c_id)

#------------------------------------------------------------------------------
class BasicScheduler(Scheduler):
    """XXX/bowei -- implement me!!!"""
    pass
    
#------------------------------------------------------------------------------
class Scheme:
    """A scheme describes the set of queues to be polled when a
    particular transport is pull from the scheduler"""

    def __init__(self, name, queues):
        self.name_ = name
        self.queues_ = queues

    def __repr__(self):
        return '<Scheme %s %s>' % (self.name_, self.queues_)

    def name(self):
        return self.name_

    def queues(self):
        return self.queues_
    
#------------------------------------------------------------------------------
class QueueBase:
    """Base class for the queues."""

    def __init__(self, name, priority):
        self.name_ = name
        self.priority_ = priority

    def name(self):
        return self.name_

    def priority(self):
        return self.priority_
    
    def pull(self):
        raise NotImplementedError()

    def append(self, msg):
        raise NotImplementedError()

#------------------------------------------------------------------------------
class Queue(QueueBase):
    """Priority: Stupidly simple scheme for now, priority is simply a
    numeric constant. lower number is higher priority."""
    
    def __init__(self, name, priority):
        QueueBase.__init__(self, name, priority)
        
        # A little inefficient, but queues should not be big
        self.msgs_timeout_ = []
        self.msgs_ = []

    def __len__(self):
        return len(self.msgs_)

    def __repr__(self):
        if len(self.msgs_) == 0:
            tail = None
        else:
            tail = self.msgs_[-1]
        return '<queue %d items, tail: %s>' % (len(self.msgs_), tail)

    def name(self):
        return self.name_

    def priority(self):
        return self.priority_

    @staticmethod
    def cmp_timeout(a, b):
        a = a[1]
        b = b[1]
        if a is None and b is None:
            return 0
        if a is None:
            return -1
        if b is None:
            return 1
        return -cmp(a, b)
        
    def prepend(self, msg):
        assert msg not in self.msgs_
        self.msgs_.append(msg)
        self.msgs_timeout_.append((msg, None))
        self.msgs_timeout_.sort(Queue.cmp_timeout)
        
    def append(self, msg):
        assert msg not in self.msgs_
        self.msgs_.insert(0, msg)
        self.msgs_timeout_.append((msg, None))
        self.msgs_timeout_.sort(Queue.cmp_timeout)

    def at_time(self, msg, time):
        assert msg not in self.msgs_
        self.msgs_.append(msg)
        self.msgs_timeout_.append((msg, time))
        self.msgs_timeout_.sort(Queue.cmp_timeout)

    def after_interval(self, msg, secs):
        self.at_time(msg, get_time() + secs)

    def is_empty(self):
        return len(self.msgs_) == 0

    def next_timeout(self):
        if self.is_empty():
            return None
        t = self.msgs_timeout_[-1][1]
        if t is None:
            return None
        return t - get_time()

    def timeout(self):
        if self.is_empty():
            return None

        next_timeout = self.next_timeout()
        if next_timeout is None or next_timeout > TIMEOUT_RES:
            return None

        log.debug('timeout from queue %s' % self.name())
        m, t = self.msgs_timeout_.pop()
        self.msgs_.remove(m)

        return m

    def pull(self):
        if self.is_empty():
            return None
        
        log.debug('pull from queue %s' % self.name())
        
        if len(self.msgs_) == 0:
            return None
        msg = self.msgs_.pop()

        found = False
        for m, t in self.msgs_timeout_:
            if m == msg:
                found = True
                break
        assert found
        
        self.msgs_timeout_.remove((m, t))

        return msg

#------------------------------------------------------------------------------
class VerSetDiff_Queue(QueueBase):
    """A queue which pulls directly from the version set
    information. The contents of the queue are vs_A - vs_B."""

    def __init__(self, name, vs_A, vs_B, priority = PRIORITY_LOWEST):
        QueueBase.__init__(self, name, priority)
        self.vsd_ = verset.VerSetDiff_Iter(vs_A, vs_B)

    def append(self, msg):
        self.vsd_.update(msg)

    def A_id(self):
        return self.vsd_.A_id()

    def B_id(self):
        return self.vsd_.B_id()

    def pull(self):
        try:
            msg = self.vsd_.next()[0]
            return msg
        except StopIteration:
            return None
